1. Field of the Invention
The present invention relates to peripheral processors, and more particularly, to processors for processing a hierarchical data structure.
2. Background Information
Computer systems often include peripheral processors to increase the computational speed of the overall system. Peripheral processors are typically specialized to efficiently perform one or more functions. Ore such peripheral processor is a graphics processor which is designed to create, modify and display a graphics data base under the control of a main or "host" computer.
Graphics processors are used in a variety of applications. For example, interactive computer-aided design (CAD) systems often utilize graphics processors to store and display a model of the object or objects to be designed. The designer directs the system through various input devices to create the model, often on a "piece" by "piece" basis. The various pieces of the model form a graphics data base which is stored by the graphics processor and displayed on command. Changes to the model by the designer cause the system to modify the data base and update the display screen to display the modified model.
One format for storing a graphics data base is referred to as a "hierarchical display list" in which graphics data describing various objects (or pieces of the objects) are stored in "segments". Each segment can be thought of as representing an object. Each segment can have one or more segments associated with it in a parent/child relationship. The "child" segment of a "parent" segment may in turn have one or more child segments associated with it. This parent/child relationship between segments results in a hierarchical "tree" structure such as that shown in FIG. 2.
Each segment of a hierarchical graphics data base typically has structural information which includes "pointers" to parent, child and "sibling" segments. Sibling segments are those segments having the same parent segment. A "pointer" to a segment identifies the starting memory location of that segment. In addition to the structural data, each segment may also contain graphics primitives and attributes of those primitives. A graphics primitive is typically a simple planar object such as a polygon or a vector defined by a list of coordinates in a convenient three dimensional coordinate system for that particular graphics primitive. The attributes data for a graphics primitive might define the color or other characteristics of the primitive, and also includes a transformation matrix which specifies the spatial position and orientation of the graphics primitive of the segment with respect to the coordinate system of the parent segment. A feature of a hierarchical graphics data base is that attribute information if not different from the parent segment, need not be defined in the child segment but can instead be "inherited" from the parent segment.
A graphics processor, in response to commands from the host computer, can create, copy or delete segments of the hierarchical data base which is typically stored in a separate memory of the graphics processor. The graphics processor further can delete, add or modify various graphics data such as the attributes, graphics primitives and transformation matrix within each segment in response to host level commands. Once the hierarchical data base has been completed, the processor reads and processes the graphics data base, producing images on the display screen of the objects represented by the graphics data base, as viewed through a "viewport" defined by the host computer. In reading the graphics data base, the graphics processor "traverses" the data base by reading data at one segment of the data base and then moving to a relative (either parent, child or sibling) segment identified by the segment pointers, in accordance with a traversal algorithm. In this manner, the graphics processor traverses the tree until the display list has been processed.
Sophisticated graphics processors can perform a number of processing functions on the graphics data of the segments. One important function is to test the graphics primitives of the segment to determine whether the primitives are within the field of view defined by the viewport. If not, the segment and its children can be ignored for purposes of further processing.
Additional graphics data processing includes concatenation of transformation matrices to produce a transformation matrix for each segment which can transform the graphics primitive coordinate set of the segment into the coordinate set of the viewport segment at the "top" of the tree. Also, the graphics processor can "clip" partially visible graphics primitives so that those portions of any primitives extending outside the field of view are not processed.
Graphics primitives which are defined in three dimensions are typically projected from the three dimensions to a two dimensional image plane of the display. Two principal projection techniques are parallel and perspective. Parallel projection can be performed by simply ignoring the third coordinate (depth) of the three dimensional coordinate set. Alternatively, perspective projection can be performed by dividing the components of the first two coordinates by the third component to give the effect of a diminishment in size for those primitives which are farther from the viewer.
Once the graphics primitives have been clipped and projected, the graphics processor converts the coordinates to the "hardware coordinates" used to display the primitives on the display screen. From the hardware coordinates, the primitives are "rasterized" which converts the hardware coordinates of the primitives into collections of pixels. Rearward facing polygon primitives are removed from further processing by the processor.
In addition, visible surfaces may be "shaded" utilizing a variety of techniques. One technique is to simply use the color attribute defined in the segment of each primitive. A second shading technique utilizes the depth of each pixel to compute an attenuation factor for the pixel. For example, primitives which are close to the viewer might be displayed at the color specified in the segment attributes. The further a primitive lies from a viewer, the darker the shade of the attribute color selected. Such a shading technique is often referred to as "depth cueing". A third type of shading is done by modeling a light source and calculating a shading intensity based on simple optical laws. When performed on a per primitive basis, this technique is often referred to as "flat shading". Performed on a per pixel basis, the technique is referred to as "smooth shading" and "Gouraud shading".
It can be appreciated from the above that an extensive amount of computation is often required to process and display a graphics primitive of a segment. Complex models can encompass a data base of thousands of segments. As a result, a graphics processor can require a significant amount of time to convert the data base to an image on the screen.
To enhance the speed at which an image may be generated, many graphics processors utilize in addition to a main CPU, one or more specially designed co-processors often referred to as "geometry processors", to perform many of the arithmetic operations required for culling, clipping, transformation of matrices, etc. However, for many such prior graphics processors, it may still require as long as 20 seconds for large data bases to update the images on the screen once the data in the graphics data base has been changed. In many applications such a delay can seriously hamper the effectiveness of the graphics processor. For example, in computer-aided design systems, waiting 20 seconds for the display to update once a change has been input can be quite annoying and an inefficient use of the designer's time. For other applications in which changes in the data need to be displayed on more of a real time basis, a slow responding graphics processor may be entirely unusable. Thus, it is seen that a significant improvement in graphics processing speed is needed.